﻿#include <iostream>

using namespace std;

#define SPLIT_CHARACTER '#'

static char* getManacherStr(const char* str)
{
	size_t originalSize = strlen(str);
	char* targetStr = (char*)malloc(originalSize * 2 + 2);
	int targetIndex = 0;
	for (int i = 0; i < originalSize; i++)
	{
		targetStr[targetIndex++] = SPLIT_CHARACTER;
		targetStr[targetIndex++] = str[i];
	}

	targetStr[targetIndex++] = SPLIT_CHARACTER;
	targetStr[targetIndex++] = 0;
	return targetStr;
}

static int maxRadius = 0;

static void setMaxRadius(int radius)
{
	maxRadius = radius > maxRadius ? radius : maxRadius;
}

static int maxPalindromeLength(const char* str)
{
	if (!str) return 0;
	size_t strSize = strlen(str);
	if (strSize == 0) return 0;
	if (strSize == 1) return 1;

	char* manacherStr = getManacherStr(str);
	size_t manacherStrSize = strlen(manacherStr);
	int* radiusArr = (int*)malloc(manacherStrSize * sizeof(int));
	for (int i = 0; i < manacherStrSize; i++)
	{
		radiusArr[i] = 1;
	}

	//           L'    R'
	// ... X  X (X  X  X) X  X  X  X  X  X  X  X  X ...
	//        L     i'       C        i     R

	// ...  c| p  a  b  c  b  a  m  a  b  c  b  a  p |n  ...

	int R = 0;
	int C = 0;
	int L = 0;
	int index = 0;
	int edge = 0;
	int index1 = 0;
	int L1 = 0;
	int R1 = 0;

	while (index < manacherStrSize)
	{
		if (index >= R)
		{
			edge = 1;
			while (index - edge >= 0 && manacherStr[index - edge] == manacherStr[index + edge])
			{
				C = index;
				R = index + edge;
				L = index - edge;
				radiusArr[index] = edge + 1;
				setMaxRadius(radiusArr[index]);
				++edge;
			}

			++index;
			continue;
		}

		index1 = 2 * C - index;
		L1 = index1 - radiusArr[index1] + 1;
		
		if (L1 > L)
		{
			radiusArr[index] = radiusArr[index1];
		}
		else if (L1 < L)
		{
			radiusArr[index] = R - index + 1;
		}
		else
		{
			edge = R - index + 1;
			while (index - edge >= 0 && manacherStr[index - edge] == manacherStr[index + edge])
			{
				C = index;
				R = index + edge;
				L = index - edge;
				radiusArr[index] = edge + 1;
				setMaxRadius(radiusArr[index]);
				++edge;
			}
		}

		++index;
	}

	free(manacherStr);
	free(radiusArr);

	return maxRadius - 1;
}

/**
 * 字符串str中, 最长回文子串的长度如何求解?
 * 如何做到时间复杂度O(N)完成?
 *
 * 4个概念:
 * 1. 每个字符位置的回文直径和回文半径
 * 2. 每个字符位置的回文直径的数组
 * 3. 最右的回文半径右端的位置R
 * 4. 最右的回文半径右端的位置R时，回文中央字符的位置C, R和C同时更新
 *
 * 需要先将原字符串加工一下，比如"a121b11311c", 加工为"#a#1#2#1#b#1#1#3#1#1#c#",
 * 即使用一个特殊字符将每个字符间隔开，并且在首尾也加入这个特殊字符.
 * 这样做可以同时处理类似"abcba"和"abccba"，即回文字符数量为奇数或偶数的两种情况。
 *
 * 字符串回文直径数组举例: "122131221"
 *    #  1  #  2  #  2  #  1  #  3  #  1  #  2  #  2  #  1  #
 * [  1  3  1  3  9  3  1  3  1 19  1  3  1  3  9  3  1  3  1  ]
 *
 * R举例:
 * 一开始R=-1, C=-1
 *
 *        #  1  #  2  #  2  #  1  #  3  #  1  #  2  #  2  #  1  #
 * index: 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18
 *
 *        #  1  #  2  #  2  #  1  #  3  #  1  #  2  #  2  #  1  #
 * index: 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18
 *        ↑
 *      (0-0), 0 > -1, ∴R=0,C=0
 *
 *        #  1  #  2  #  2  #  1  #  3  #  1  #  2  #  2  #  1  #
 * index: 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18
 *           ↑
 *          (0-2), 2 > 0, ∴R=2,C=1
 *
 *        #  1  #  2  #  2  #  1  #  3  #  1  #  2  #  2  #  1  #
 * index: 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18
 *              ↑
 *             (2-2), 2 == 2, ∴R和C不更新
 *
 *        #  1  #  2  #  2  #  1  #  3  #  1  #  2  #  2  #  1  #
 * index: 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18
 *                 ↑
 *               (2-4), 4 > 2, ∴R=4,C=3
 *
 *        #  1  #  2  #  2  #  1  #  3  #  1  #  2  #  2  #  1  #
 * index: 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18
 *                    ↑
 *                   (0-8), 8 > 4, ∴R=8,C=4
 * ......
 *
 *
 * 假设某个C位置，最右侧是R:
 *
 * ...[ X  X  X  X  X  X  X  X  X  X  X  X  X  ]...
 *      L        i'       C        i        R
 * 以C为中心，左到L，右到R属于回文范围，设i'为i点以C为中心的对称点。
 *
 * 情况1：
 * ...[ X  X  X  X  X  X  X  X  X  X  X  X  X  ]  X  X  X
 *      L        i'       C                 R        i
 * 如果i不在L-R的范围内，直接左右暴力扩，看看是否有回文结构
 * 情况2：
 * 如果i在L-R的范围内，
 * (1) 如果i'的回文结构在L-R内，则i的回文结构必定和i'对称，也就是i'的回文字符串的逆序。
 * ...[ X  X (X  X  X) X  X  X  X  X  X  X  X  ]...
 *      L        i'       C        i        R
 *
 * (2) 如果i'的回文结构超过了L-R范围, 则i的回文结构的最右端一定是R。
 * ...X (X  [ X  X  X  X  X  X  X  X) X  X  X  X  X  ]...
 *            L        i'       C        i        R
 *
 * (3) 如果i'的回文结构的左边界刚好是L, 则i的回文结构的右边界至少能到R，但是再往右是否是回文结构，需要继续外扩判断。
 * ...[(X  X  X  X  X  X  X) X  X  X  X  X  X  X  X  ]  X  X...
 *      L        i'          C           i        R     ↑
 *
 *
 */
int main_Palindrome()
{
	char str[256] = "abccbaqwertyuytrewq";
	char* manacherStr = getManacherStr(str);
	int maxLen = maxPalindromeLength(str);
	printf("res=%d\n", maxLen);
	return 0;
}